//给你一个会议时间安排的数组 intervals ，每个会议时间都会包括开始和结束的时间 intervals[i] = [starti, endi] ，返回 
//所需会议室的最小数量 。 
//
// 
//
// 示例 1： 
//
// 
//输入：intervals = [[0,30],[5,10],[15,20]]
//输出：2
// 
//
// 示例 2： 
//
// 
//输入：intervals = [[7,10],[2,4]]
//输出：1
// 
//
// 
//
// 提示： 
//
// 
// 1 <= intervals.length <= 10⁴ 
// 0 <= starti < endi <= 10⁶ 
// 
// Related Topics 贪心 数组 双指针 排序 堆（优先队列） 👍 435 👎 0

package leetcode.editor.cn;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class _253_MeetingRoomsIi {
    public static void main(String[] args) {
        Solution solution = new _253_MeetingRoomsIi().new Solution();
//        int[][] intervals = {{0, 30},{5, 10},{15, 20}};
//        int[][] intervals = {{1, 10}, {2, 7}, {3, 19}, {8, 12}, {10, 20}, {11, 30}};
        int[][] intervals = {{1293,2986}, {848,3846}, {4284,5907}, {4466,4781}, {518,2918}, {300,5870}};
//        int[][] intervals = {{7, 10}, {2, 4}};
        System.out.println(solution.minMeetingRooms(intervals));
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int minMeetingRooms(int[][] intervals) {
            Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
            for (int[] interval : intervals) {
                System.out.println(Arrays.toString(interval));
            }
            List<Integer> room = new ArrayList<>();
            for (int i = 0; i < intervals.length; i++) {
                int start = intervals[i][0];
                boolean flag = false;
                for (int j = 0; j < room.size(); j++) {
                    if (start >= room.get(j)) {
                        room.set(j, intervals[i][1]);
                        flag = true;
                        break;
                    }
                }
                if (!flag) {
                    room.add(intervals[i][1]);
                }
            }
            return room.size();
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}